Introduction to ZK-STARKs

(updated )

Remco Bloemen remco@0x.org

$$ \def\F{\mathtt {F}} \def\X{\mathtt {X}} \def\Y{\mathtt {Y}} \def\Z{\mathtt {Z}} $$

Disclaimer: contains math

Zero knowledge proofs

We know some algorithm $\F(\X, \Y)$.

I give you $\X$ and $\Z$ and proof that “I know an $\Y$ such that $\F(\X, \Y) = \Z$” without revealing $\Y$.

Scalable DEX

“I know an $\Y$ such that $\F(\X, \Y) = \Z$”

$\F$ verifies maker and taker signatures on the trades and updates the balances.

Naive solution

Problems:

Math refresher: Polynomials
Constant$a_0$
Linear$a_0 + a_1 x$
Parabola$a_0 + a_1 x + a_2 x^2$
Cubic$a_0 + a_1 x + a_2 x^2 + a_3 x^3$
Quartic$a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4$
...$a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$

Can be uniquely described in three ways:

(* Zeros might be imaginary.)

Can do math with them:

Toy example: Fibonnacci

We want to prove the 1000-th Fibonacci number starting from a public and a secret value. Take $\F(\X, \Y) = \Z$ to mean the following:

$$ \begin{aligned} F_0 &:= \X & F_i &:= F_{i - 2} + F_{i - 1} \\ F_1 &:= \Y & \Z &:= F_{1000} \\ \end{aligned} $$

Computational trace

Computation with $n$ steps and $w$ registers. The trace $T$ is a $n × w$ table. Here $n = 1000$ and $w = 2$. Restate algorithm as constraints on $T_{i}$

Example: $\X = 3$, $\Y = 4$:

n$T_{n, 0}$$T_{n, 1}$
034
147
2711
31118
.........
999$F_{999}$$F_{1000}$

Encode the algorithm as a set of transition constraints:

$$ \begin{aligned} T_{i + 1, 0} &= T_{i, 1} & T_{i + 1, 1} &= T_{i, 0} + T_{i, 1} \end{aligned} $$

and boundary constraints:

$$ \begin{aligned} T_{0, 0} &= \X & T_{999, 1} &= \Z & \end{aligned} $$

‟I know $y$ such that $f(x,y)=z$.”

$⇔$

‟I know a trace $T$ such that the constraints hold.”

Trace polynomials

For each register $j$, create a polynomial $P_j(x)$ of degree $999$ such that $P_j(i) = T_{i, j}$ for $i = 0 … 999$.

(Actual implementation uses $P_j(ω^i) = T_{i, j}$ with $ω$ a $n$-root of unity to allow $O(n \log n)$ FFT and FRI. Also rounds $n$ up to the next power of two. Ignore for now.)

Consider the constraint $T_{i + 1, 1} = T_{i, 0} + T_{i, 1}$ for $i = 0 … 999$:

$⇔ P_1(i + 1) = P_0(i) + P_1(i)$ for $i = 0 … 999$

$⇔ P_1(i + 1) - (P_0(i) + P_1(i)) = 0$ for $i = 0 … 999$

$⇔ Q(x) = P_1(x + 1) - (P_0(x) + P_1(x))$ is zero when $x$ is an integer $0 … 999$.

$R(x) = (x - 0) ⋅ (x - 1)⋅ (x - 2) ⋯ (x - 999)$ is a polynomial and is zero only when $x$ is an integer $0 … 999$.

This means

$$ C(x) = \frac{Q(x)}{R(x)} $$

is also a polynomial.

Create functions that are polynomial only when the constraints are satisfied:

Transition constraints:

$$ \begin{aligned} T_{i + 1, 0} &= T_{i, 1} &⇒&& C_0(x) &= \frac {P_0(x + 1) - P_1(x)} {\prod^i_{[0 … 998]}\left( x - i\right)} \\ T_{i + 1, 1} &= T_{i, 0} + T_{i, 1} &⇒&& C_1(x) &= \frac {P_1(x + 1) - (P_0(x) + P_1(x))} {\prod^i_{[0\dots998]}\, (x - i)} \end{aligned} $$

Boundary constraints:

$$ \begin{aligned} T_{0, 0} &= X &⇒&& C_2(x) &= \frac {P_0(x) - X} {x - 0} \\ T_{999, 1} &= Z &⇒&& C_3(x) &= \frac {P_1(x) - Z} {x - 999} \\ \end{aligned} $$

‟I know $y$ such that $f(x,y)=z$.”

$⇔$

‟I know a trace $T$ such that the constraints hold.”

$⇔$

‟I know polynomials $P_0$ and $P_1$ such that $C_0$, $C_1$, $C_2$, $C_3$ are polynomial.”

Interactive proof

I give you $\X$, $\Z$ and a merkle roots of $P_0$ and $P_1$.

You give me random values $α_0$, $α_1$, $α_2$, $α_3$.

Fast Reed-Solomon Interactive Oracle Proof II

$$ P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x ^3 \cdots + a_n x^n $$

Given a random number $β$, we can fold the coefficients and get a polynomial of degree $\frac{n}{2}$.

$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} + a_n β) x^{\frac n2} $$

This can be computed using:

$$ P'(x) = P(x) + \left( \frac{β}{2x} - \frac{1}{2}\right) \left(P(x) - P(-x) \right) $$

$$ P(x) = a_0 + a_1 x + a_2 x^2 + a_3 x ^3 \cdots + a_n x^n $$

Given a random number $β$, we can fold the coefficients and get a polynomial of degree $\frac{n}{2}$.

$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} a_n β) x^{\frac n2} $$

$$ P'(x) = P(x) + \left( \frac{β}{2x} - \frac{1}{2}\right) \left(P(x) - P(-x) \right) $$

$$ \begin{aligned} P(x) ={}& a_0 &{}+{}& a_1 x &{}+{}& a_2 x^2 &{}+{}& a_3 x ^3 &{}+{}& \cdots &{}+{}& a_{n-1} x^{n-1} &{}+{}& a_n x^n \\ P(-x) ={}& a_0 &{}-{}& a_1 x &{}+{}& a_2 x^2 &{}-{}& a_3 x ^3 &{}+{}& \cdots &{}-{}& a_{n-1} x^{n-1} &{}+{}& a_n x^n \\ P(x) - P(-x) ={}& && 2a_1 x && &{}+{}& 2a_3 x ^3 &{}+{}& \cdots &{}+{}& 2 a_{n-1} x^{n-1} \\ \\ \frac{β}{2x} \left(P(x) - P(-x)\right) ={}& a_1 β && &{}+{}& a_3 β x^2 && &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-2} \\ \\ \frac{1}{2} \left(P(x) - P(-x)\right) ={}& a_1 x && &{}+{}& a_3 x^3 && &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-1} \\ \\ (\frac{β}{2x}-\frac{1}{2}) \left(P(x) - P(-x)\right) ={}& a_1 β &{}-{}& a_1 x &{}+{}& a_3 β x^2 &{}-{}& a_3 x^3 &{}+{}& \cdots &{}+{}& a_{n-1} β x^{n-1} \\ \end{aligned} $$

$$ P'(x) = (a_0 + a_1 β) + (a_2 + a_3 β) x + \cdots + ( a_{n-1} + a_n β) x^{\frac n2} $$

I compute $C(x) = α_0 ⋅ C_0(x) + α_1 ⋅ C_1(x) + α_2 ⋅ C_2(x) + α_3 ⋅ C_3(x)$.

I give you the merkle root of $C$ and claim $\deg C = 1024$.

You give me a random value $𝛽_0$.

I give you the merkle root of $C'$ and claim $\deg C' = 512$.

You give me a random value $𝛽_1$.

...

I give you the constant $C''$.

You verify $C''$ using $\X$, $\Y$, the $α$s and the $𝛽$s.

Fiat-Shamir transform

All you do is give me random numbers. Why don't I replace you by a pseudo random number generator!

Seed PRNG with all prover messages, extract random 'verfier' messages.

Send all the proof at once.

Remco Bloemen
Math & Engineering
https://2π.com